#include <bits/stdc++.h>

using namespace std;

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
    // 提交以下的方法
	// 如果测试数据量变大了就修改这个值
    static const int MAXN = 101;
    TreeNode* q[MAXN];
    int l, r;

public:
    bool isCompleteTree(TreeNode* root) 
    {
        if(root == nullptr) return true;

        l = r = 0;
        q[r++] = root;
		// 是否遇到过左右两个孩子不双全的节点
        bool leaf = false;
        while(l < r)
        {
            root = q[l++];
            if((!root->left && root->right) || (leaf && (root->left || root->right)))
            {
                return false;
            }
            if(root->left) q[r++] = root->left;
            if(root->right) q[r++] = root->right;
            if(!root->left || !root->right) leaf = true;
        }

        return true;
    }
};

// 另一种方法
class Solution 
{
    // 提交以下的方法
	// 如果测试数据量变大了就修改这个值
    // 因为空节点也要进队列，所以空间要大一些
    static const int MAXN = 200;
    TreeNode* q[MAXN];
    int l, r;

public:
    bool isCompleteTree(TreeNode* root) 
    {
        if(root == nullptr) return true;

        l = r = 0;
        q[r++] = root;
        while(l < r)
        {
            root = q[l++];
            // 遇到空节点，后面如果再遇到非空节点
            // 就不是完全二叉树了
            if(root == nullptr)
            {
                while(l < r)
                {
                    root = q[l++];
                    if(root) return false;
                }
                return true;
            }
            // 空节点也要进队列
            q[r++] = root->left;
            q[r++] = root->right;
        }
        return true;
    }
};